package class04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.Map.Entry;
import java.util.TreeMap;

/**
 * 题目：天际线问题
 * 
 * 描述：
 * 城市的天际线是从远处观看该城市中所有建筑物形成的轮廓的外部轮廓。
 * 给你所有建筑物的位置和高度，请返回由这些建筑物形成的天际线。
 * 
 * 每个建筑物的几何信息用三元组 buildings[i] = [lefti, righti, heighti] 表示：
 * - lefti 是第i座建筑物左边缘的x坐标
 * - righti 是第i座建筑物右边缘的x坐标
 * - heighti 是第i座建筑物的高度
 * 
 * 你可以假设所有的建筑都是完美的长方形，在高度为0的绝对平坦的表面上。
 * 天际线应该表示为由"关键点"组成的列表，格式 [[x1,y1],[x2,y2],...]，并按x坐标进行排序。
 * 关键点是水平线段的左端点。列表中最后一个点是最右侧建筑物的终点，y坐标始终为0，仅用于标记天际线的终点。
 * 
 * 示例：
 * 输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
 * 输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]
 * 
 * 解题思路：
 * 使用扫描线算法结合TreeMap来解决这个问题。
 * 1. 将每个建筑物的左右边缘分别表示为"进入"和"离开"事件
 * 2. 按照x坐标对所有事件进行排序
 * 3. 使用TreeMap维护当前所有活跃建筑物的高度及其出现次数
 * 4. 遍历所有事件，更新高度信息并记录关键点
 */
// 本题测试链接 : https://leetcode.com/problems/the-skyline-problem/
public class Code08_TheSkylineProblem {

	/**
	 * 表示建筑物边缘的节点类
	 * 用于记录扫描线算法中的事件点
	 */
	public static class Node {
		public int x;          // x坐标
		public boolean isAdd;  // true表示建筑物开始，false表示建筑物结束
		public int h;          // 建筑物高度

		public Node(int x, boolean isAdd, int h) {
			this.x = x;
			this.isAdd = isAdd;
			this.h = h;
		}
	}

	/**
	 * 节点比较器，按照x坐标升序排列
	 */
	public static class NodeComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
			return o1.x - o2.x;
		}
	}

	/**
	 * 计算建筑物形成的天际线
	 * 
	 * @param matrix 建筑物信息数组，每个元素为 [left, right, height]
	 * @return 天际线关键点列表
	 */
	public static List<List<Integer>> getSkyline(int[][] matrix) {
		// 将每个建筑物转换为两个事件节点：开始和结束
		Node[] nodes = new Node[matrix.length * 2];
		for (int i = 0; i < matrix.length; i++) {
			// 建筑物开始事件
			nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);
			// 建筑物结束事件
			nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);
		}
		
		// 按照x坐标对事件节点进行排序
		Arrays.sort(nodes, new NodeComparator());
		
		// key: 高度, value: 该高度出现的次数
		TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
		// key: x坐标, value: 该x坐标处的最大高度
		TreeMap<Integer, Integer> mapXHeight = new TreeMap<>();
		
		// 遍历所有事件节点
		for (int i = 0; i < nodes.length; i++) {
			if (nodes[i].isAdd) {
				// 如果是建筑物开始事件，增加对应高度的计数
				if (!mapHeightTimes.containsKey(nodes[i].h)) {
					mapHeightTimes.put(nodes[i].h, 1);
				} else {
					mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) + 1);
				}
			} else {
				// 如果是建筑物结束事件，减少对应高度的计数
				if (mapHeightTimes.get(nodes[i].h) == 1) {
					mapHeightTimes.remove(nodes[i].h);
				} else {
					mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) - 1);
				}
			}
			
			// 更新当前x坐标的最大高度
			if (mapHeightTimes.isEmpty()) {
				// 如果没有活跃的建筑物，高度为0
				mapXHeight.put(nodes[i].x, 0);
			} else {
				// 否则取当前最高建筑物的高度
				mapXHeight.put(nodes[i].x, mapHeightTimes.lastKey());
			}
		}
		
		// 根据高度变化生成关键点
		List<List<Integer>> ans = new ArrayList<>();
		for (Entry<Integer, Integer> entry : mapXHeight.entrySet()) {
			int curX = entry.getKey();
			int curMaxHeight = entry.getValue();
			// 只有当高度发生变化时才添加关键点
			if (ans.isEmpty() || ans.get(ans.size() - 1).get(1) != curMaxHeight) {
				ans.add(new ArrayList<>(Arrays.asList(curX, curMaxHeight)));
			}
		}
		return ans;
	}

}
